IEEE 802.1ad (as well as IEEE 802.1d) provides a method by which Network Elements (NEs) learn the locations of MAC addresses. A forwarding tree is generated, which includes all the nodes (NEs, host nodes, etc) in the network. Each NE also maintains a mapping of MAC addresses to ports on the NE. When an NE receives a packet for an unknown destination the NE broadcasts the packet to all of the next nodes in the tree, if any. The NE also notes from over which port the packet came, and if the source MAC address of the packet is also unknown the NE updates its mapping (also known as a forwarding table) to relate the MAC address and the port. Eventually the NE supporting the destination MAC address receives the packet and forwards the packet to its attachment circuit. In this way, traffic to an unknown destination MAC address eventually reaches the appropriate host node. Each NE also learns over which port the source MAC address can be reached, and subsequent packets destined for the source MAC address are sent only over the port indicated by the mapping, rather than being broadcast over the tree.
The method provided by IEEE 802.1ad provides for address learning of MAC addresses and forwarding of packets to the appropriate host nodes. Being tree-based, the forwarding of packets having an unrecognized address avoids loops. However, since the address learning of IEEE 802.1ad is tree-based, all forwarding of packets also follows the branches of the tree. There is no guarantee that the paths followed by forwarded packets are the shortest paths. Although recent improvements to IEEE 802.1ad have improved the chances that the paths in the tree represent the shortest paths, there is still no guarantee. One limitation is that generation of the tree assumes that all links are symmetric with respect to cost metrics, which may not always be the case.
Another method of providing address learning is provided by IETF full-meshed VPLS. In IETF full-meshed VPLS, all NEs are in communication with all other NEs of the network. A first NE which receives a packet having an unrecognized destination MAC address forwards the packet to every other NE. Each NE forwards the packet to its respective attachment circuit, but does not forward the packet to other NEs since the NE realizes that all other NEs have already received the packet. If the source MAC address is also unknown to an NE, the NE updates its mapping to show that the source MAC address can be reached through the port over which the packet arrived. Thereafter, any packet arriving at an NE is forwarded over the port indicated by the mapping.
Since a packet having an unrecognized source MAC address arrives directly from the NE supporting that source MAC address, IETF full-meshed VPLS provides shortest paths when learning addresses for subsequent forwarding of packets. In addition, the broadcast to all NEs in the mesh ensures that packets having an unknown destination MAC address will reach their destination. However, since the method relies on broadcast to all NEs in the network, the method does not scale very well.
Furthermore, VPLS requires all NEs to be fully connected using pseudowires, which conceptually are tunnels. If a tunnel does not work, the VPLS cannot emulate the LAN service and the VPLS is said to have only partial mesh connectivity. In such a case, a NE may black-hole traffic intended for another NE if routers on the NEs are using OSPF or IS-IS with broadcast mode. If a first site A has working pseudowires to all sites, including a site B having a designated router, but not to a site C, site A will still receive link state advertisements from a router at site C via the designated router at site B. However, no data can be sent from site A to site C since there is no working pseudowire between site A and site C, and site A will not realize that no traffic is reaching site C.
Yet another method of address learning is RBridges, described in Perlman et al., “RBridges: Transparent Routing”, IETF Network Working Group Internet Draft, draft-perlman-rbridge-02.txt, Feb. 19, 2005. However, RBridges provide no mechanism for sending known frames on a tree in the event that a direct link fails and a NE is unreachable, although RBridge does send unknown destination MAC addresses on a tree. In other words, RBridges would also have the partial mesh connectivity problem.
A method of combining the tree nature for address learning with the fully-meshed aspect of data delivery would ensure robust address learning in the event of link failure, while ensuring that data is delivered over shortest paths.